package com.zklh.leetcode.other.problem1;

/**
 * @ClassName MaxArea
 * @Description
 * @Author 坐看落花
 * @Date 2019/7/15 20:25
 * @Version 1.0
 **/
public class MaxArea {

    /**
     * 最大面积算法1, 暴力循环
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int maxValue = 0;
        for(int i = 0; i < height.length-1; i++){
            for(int j = i+1; j < height.length; j++){
                int tmpValue = (j-i)*min(height[i],height[j]);
                maxValue = tmpValue > maxValue ? tmpValue: maxValue;
            }
        }
        return maxValue;
    }

    /**
     * 最大面积实现算法2, 优于算法1
     * 大致思路, 缩小范围, 先让临时最大面积是最两边高度的夹击面积, 然后向里缩小范围, 如果有比当前最大面积更大的
     * 情况, 则是从较短边一边缩小范围, 因为如果从较大边缩小范围, 从该范围内取一边与较小边组成的面积一定比现在的
     * 临时最大面积小, 所以可以直接排除该一类情况, 也就是较小边与较大边向里内的任何一个边组成的面积都小于当前临时最
     * 大面积, 可以排除
     * @return
     */
    public int maxArea_Better(int[] height){
        // 定义临时最大值
        int tmpMaxArea = 0;
        // 定义当前指针指向的两边组成的面积
        int nowArea = 0;
        // 定义左边的指针
        int left = 0;
        // 定义右边的指针
        int right = height.length - 1;
        while(left < right){
            tmpMaxArea = nowArea > tmpMaxArea ? nowArea : tmpMaxArea;
            if(height[left] > height[right]){
                nowArea = height[right] * (right - left);
                right--;
            }else{
                nowArea = height[left] * (right - left);
                left++;
            }
        }
        return tmpMaxArea;
    }

    public int min(int x, int y){
        return x<y?x:y;
    }

    public static void main(String[] args){
        MaxArea maxArea = new MaxArea();
        int[] arr = new int[]{1,8,6,2,5,4,8,3,7};
        System.out.println(maxArea.maxArea_Better(arr));
    }
}
